package training;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;

/**
 * @Author liangzai
 * @Description:
 */
public class J25_5_7_Training {
    //二叉树的所有路径
    public List<String> ret ;
    public List<String> binaryTreePaths(TreeNode root) {
        ret = new ArrayList<>();
        StringBuffer stringBuffer = new StringBuffer("");
        dfs1(root,stringBuffer);
        return ret;
    }

    public void dfs1(TreeNode root, StringBuffer stringBuffer){
        if(!stringBuffer.toString().equals("")){
            stringBuffer.append("->");
        }
        stringBuffer.append(root.val);
        if(root.right == null && root.left == null){
            ret.add(stringBuffer.toString());
            return ;
        }
        StringBuffer stringBufferleft = new StringBuffer(stringBuffer.toString());
        if(root.right != null){
            dfs1(root.right,stringBuffer);
        }
        if (root.left != null) {
            dfs1(root.left,stringBufferleft);
        }
    }

    //全排列
    public List<List<Integer>> retList;
    public HashSet<Integer> set ;
    public List<List<Integer>> permute(int[] nums) {
        retList = new ArrayList<>();
        set = new HashSet<>();
        List<Integer> path = new ArrayList<>();
        dfs(path,nums);
        return retList;
    }

    public void dfs(List<Integer> path,int[] nums){
        int n = nums.length;
        if(path.size() == n){
            retList.add(path);
            return ;
        }
        for (int i = 0; i < n; i++) {
            if(!set.contains(nums[i])) {
                path.add(nums[i]);
                set.add(nums[i]);
                dfs(new ArrayList<>(path),nums);
                set.remove(path.get(path.size()-1));
                path.remove(path.size()-1);
            }
        }
    }

//    public static void main(String[] args) {
//        HashSet<List<Integer>> set = new HashSet<>();
//        List<Integer> list1 = new ArrayList<>();
//        list1.add(2);
//        list1.add(1);
//        list1.add(5);
//        List<Integer> list2 = new ArrayList<>();
//        list2.add(2);
//        list2.add(1);
//        list2.add(5);
//        set.add(list1);
//        set.add(list2);
//        System.out.println(set.toString());
//    }
}










